package sort;

import java.util.Arrays;

public class InsertSort {
    /*
    * 插入排序，时间复杂度为 O(n) ~ O(n^2)
    * 空间复杂度为 O(1)
    * */
    public static void insetSort(int[] arr){
        int n = arr.length;

        // 外层循环的i，是指有序数组的长度，也指的是当前需要插入的数组元素下标
        for(int i=1; i<arr.length; i++){
            int key = arr[i];
            int j=i-1;
            // 从后向前遍历有序的这部分数组，如果比需要插入的元素大，则向后移动一个位置，预留出插入的位置
            while(j>=0 && arr[j] > key){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = key;

        }
    }

    public static void main(String[] args){
        int[] arr = {5, 4, 3, 2, 1};
        InsertSort.insetSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
